#include "T9Trie.h"
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <conio.h>
using namespace std;

void T9Trie::addWord(int index) {
	string word=dictionary[index];
	 int len = word.length();
	 Node* currentNode = root;  
	 for ( int i = 0; i <len; ++i ) {
		 int letterIndex=word[i]-'a';
		 if (letterIndex<0 || letterIndex>25) {
			 string error = "The word \"";
			 error.append(word);
			 error.append("\"contains symbols which are not in alphabet."); 
			 throw new std::exception( error.c_str() );
		 }
		 int charIndex = phone[word[i]]; //индекс в массиве латинских букв
		 if ((charIndex < 0) || (charIndex > A_SIZE - 1)) {
			 string error = "The word \"";
			 error.append(word);
			 error.append("\"contains symbols which are not in alphabet."); 
			 throw new std::exception( error.c_str() );
		 }
		 
		 if (currentNode->go[0]==0) {
			 currentNode->go[0]=root;
		 }
        if (currentNode->go[charIndex] == 0) { // если еще нет перехода по этой букве, то созадем новый узел
			currentNode->go[charIndex] = new Node;
			currentNode->go[charIndex]->path=currentNode->path+char(charIndex+'0');
        }
        // переходим по букве в следующий узел
        currentNode = currentNode->go[charIndex];
    }

	currentNode->leafPatternNumber.push_back(index);
	if (currentNode->numberWord==-1 || freq[currentNode->numberWord]<freq[index]) {
		currentNode->numberWord=index;
	}
    //currentNode->numberWord=index; // добавляем слово в массив слов, которым соответствует эта вершина
	currentNode->leaf=true; // вершина лист
}

void T9Trie::buildAutomat() {
	if (root!=0) {
		deleteNode(root);
	}
	queue<Node*> queue;
    root = new Node;
	root->suffLink = root;

	// добавляем слова в бор

	int size=dictionary.size();
	for ( int i = 0; i < size; ++i ) {
		addWord(i);
	}

	// задаем суффиксные ссылки для узлов, в которы переходим из корня
	
	for ( int i=0; i<A_SIZE; ++i ) {
		if ( root->go[i] != 0 ) {
			root->go[i]->suffLink = root;
			queue.push(root->go[i]);
		} else {
			root->go[i] = root;
		}
	}
	

	/*// запускаем для присвоения значений суффиксным ссылкам
	while ( !queue.empty() ) {
		Node* currentNode = queue.front();
		queue.pop();
		
		// вычисляем для потомков, так как для вершины вычислено на одном из предыдущих шагов
		for ( int i=0; i<A_SIZE; i++ ) {
			if ( currentNode->go[i]!=0 ) {
				Node* childNode = currentNode->go[i];
				queue.push(childNode);
				Node* suff = currentNode->suffLink;

				// суффиксный предок, у которого есть ребро по нужному символу
				while ( suff->go[i] == 0 ) {
					suff = suff->suffLink;
				}
				childNode->suffLink = suff->go[i];
				
				// сливаем массивы соответтсвущих слов
				childNode->leafPatternNumber.insert( childNode->leafPatternNumber.begin(), childNode->suffLink->leafPatternNumber.begin(), childNode->suffLink->leafPatternNumber.end());
			}
		}
	}*/

	chooseWord(root);
}


void T9Trie::chooseWord(Node* node) {
	//vector<int> words;
	for (int i=1; i<A_SIZE; i++) {
		if (node->go[i]!=0 && node->go[i]!=root) {
			chooseWord(node->go[i]);
			if (node->numberWord==-1 || freq[node->numberWord]<freq[node->go[i]->numberWord]) {
				node->numberWord=node->go[i]->numberWord;
			}
		}	
	}

	//cout<<"for "<<node->path<<" numberword "<<node->numberWord<<endl;
}
void T9Trie::search() {
	if ( root==0 ) {
		throw new exception("Trie is empty");
	}
	
	Node* currentNode = root; 

	bool work=true;

	while (work) {
		char c=getch();
		if (int(c)==13) {
			break;
		}
		int charIndex=c-48;
		if (charIndex<0 || charIndex>9 || charIndex==1) {
			cout<<"wrong symbol"<<endl;
			currentNode=root;
			continue;
		}

		if (charIndex==0) {
			currentNode=root;
		} else {
		
			// переход в нужное состояние по данному символу
			if (currentNode->go[charIndex]==0) {
				cout<<"No words in dictionary for this combination"<<endl;
				currentNode=root;
				continue;
			} else {
				currentNode = currentNode->go[charIndex];
				int word=currentNode->numberWord;
				if (word!=-1) {
				cout<<dictionary[word]<<endl;
				}
			}
		}
		
	}
}


void T9Trie::deleteNode(Node* node) {
	if (node == 0) {
		return;
	} 
    for ( int i = 0; i < A_SIZE; ++i ) {
		if ((node->go[i]!=0) && ( node->go[i]!=node )) {
			delete node->go[i];
		}
	}
	if (node != 0) {
		delete node;
	}
}